
class Livestock:
    def __init__(self, 
        cows: list, number_of_rules: int, 
        x_cows: list, y_cows: list, ans: list):
        self.cows = cows
        self.number_of_rules = number_of_rules
        self.x_cows = x_cows
        self.y_cows = y_cows
        self.ans = ans
    
    # 判断 name 奶牛的名字是否在 ans 中，
    # 如果在，就返回它在 ans 里的索引，
    # 如果不在，就返回 -1。
    def get_index(self, name: str) -> int:    
        for i in range(0, len(self.ans)):
            if name == self.ans[i]:
                return i
        return -1

    # 判断是否可以从 cows 中选择名字为 name 的牛放到 ans 里。
    def can_be_pickedup(self, name: str) -> bool:
        # 1. 如果 name 已经在 ans 里了，那么就不用再放了。
        if self.get_index(name) != -1:
            return False # name 已经在 ans 里了
        
        nbr = 0 # name 的邻居，邻居就是必须挨在一起挤奶的牛。

        # 计算名字为 name 的牛有多少邻居。
        # ans:  XXXXXXX X
        #                     P name
        # 找到 name 在 cows 中的位置
        for i in range(0, len(self.x_cows)):
            # name 在 x_cows 中
            if self.x_cows[i] == name and self.get_index(self.y_cows[i]) == -1:
                nbr += 1
            
            if self.y_cows[i] == name and self.get_index(self.x_cows[i]) == -1:
                nbr += 1

        if nbr == 2:
            return False

        # 有一个邻居的情况
        if len(self.ans) != 0:
            for i in range(0, len(self.x_cows)):
                if self.ans[len(self.ans) - 1] == self.x_cows[i] and self.get_index(self.y_cows[i]) == -1 and self.y_cows[i] != name:
                    return False
                
                if self.ans[len(self.ans) - 1] == self.y_cows[i] and self.get_index(self.x_cows[i]) == -1 and self.x_cows[i] != name:
                    return False

        # 没有邻居的情况
        return True

    # 计算一个满足所有挤奶顺序的 ans
    def solution(self):
        self.cows.sort()

        for i in range(0, len(self.cows)):
            # 每一次遍历，我们都要选一头合适的牛出来。
            next_cow = 0 # 下一头被选中的牛的索引

            while not self.can_be_pickedup(self.cows[next_cow]):
                next_cow += 1
            
            # next_cow 位置的名字是可以被选择的
            self.ans.append(self.cows[next_cow])

    # 执行到这里，self.ans 就是一个合法的答案

        
def parse_input(input_file_name: str) -> Livestock:
    cows = [
        "Bessie", "Buttercup", "Belinda", "Beatrice", "Bella", "Blue", "Betsy", "Sue"
    ]

    f = open(input_file_name, "r") # open 返回的类型叫做 file handle，文件句柄

    # 挤奶规则的数量: int
    number_of_rules = int(f.readline())
    x_cows = []
    y_cows = []
    for i in range(0, number_of_rules):
        r = f.readline()
        words = r.split()
        x_cows.append(words[0])
        y_cows.append(words[5])

    ans = []   # 答案，挤奶的牛的名字顺序:   list

    f.close()

    return Livestock(cows, number_of_rules, x_cows, y_cows, ans)



ls = parse_input("Lineup.in")
ls.solution()
print(ls.ans)